package com.cat.dataStructure02;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/can-make-palindrome-from-substring/
 * @create 2025/10/22 22:23
 * @since JDK17
 */

public class Solution48 {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        char[] arr = s.toCharArray();
        int n = s.length();
        int[] prefix = new int[n + 1];
        List<Boolean> ans = new ArrayList<>();
        // 前缀异或和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ (1 << arr[i] - 'a');
        }
        for (var q : queries) {
            int l = q[0], r = q[1], k = q[2];
            int x = prefix[r + 1] ^ prefix[l], y;
            if ((r - l + 1) % 2 == 0) { // 偶数
                y = (Integer.bitCount(x) + 1) / 2;
            } else {
                y = Integer.bitCount(x) / 2;
            }
            ans.add(y <= k);
        }

        return ans;
    }
}
